\documentclass[a4paper,12pt]{book}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{enumerate}
\usepackage{setspace}
\usepackage{subfigure}

%Support to portuguese
\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc}
\usepackage{hyperref}

\title{Token Ring Wireless baseado em \textit{Cluster}}
\author{Universidade de São Paulo\\ Instituto de Matemática e Estatísitica\\ Departamento de ciencia da computação\\
\vspace{1.0in} Aluno: Adroaldo Lazouriano Moreira Borges\\ Orientador: Prof. Dr. Marco Dimas Gubitoso}


\begin{document}
\maketitle
\tableofcontents

\chapter{Introdução}

\onehalfspace
Existem dois paradigmas de rede wireless. Uma rede wireless pode ser infraestruturada ou ad-hoc. Na primeira, existe normalmente um controlador centralizado
que administra toda rede. I.e., os nós em uma rede infraestruturada são isentos da responsabilidade de gerenciar o tráfego na rede, por exemplo. Se por alguma
inconveniência o controlador falhar a rede pode ficar inoperante.
Ao passo que em uma rede ad-hoc, o gerenciamento de rede é automático. As responsabilidades são distribuídas entre nós da rede. Dizemos que
redes ad-hoc wireless são coleções de dispositivos (nós) móveis equipados com radio transmissor e receptor sem fios que comunicam através de um canal comum. Também, esse tipo
de rede se denomina MANET\footnote{Mobile Ad hoc NeTwork}.\\
Os fatores queda de nós (devido a alcance de sinal curto e a  bateria com pouca carga, por exemplos), a eficiência no uso de largura de banda, controle de interferência entre os nós, 
e a limitação de latência, são alguns dos desafios em uma rede ad-hoc wireless móvel. \\
Para lidar com alguns desafios em rede ad-hoc, apresentamos o Token Ring Wireless baseado em \textit{Cluster} (TRWC). O TRWC é um sistema distribuído planejado para o controle de acesso 
ao meio (MAC\footnote{Medium Access Control}) de comunicação, e também para encaminhamento de dados entre anéis em \textit{cluster}. Em ambiente de rede ad-hoc wireless é necessário mecanismos que evitam as
colisões de pacotes (introduzidas pelo problema de \textit{hidden node}) entre os nós (as estações). Por exemplo, a tecnologia wi-fi usa os mecanismos DCF\footnote{Distributed Coordination Function}
e PCF\footnote{Point Coordination Function} para o controle de acesso ao meio ~\cite{wifispec}. Porém, nenhum desses mecanismos oferece soluções em termos de uso de meio com justiça e para evitar colisões em rede ad-hoc. 
Neste trabalho estudamos e procuramos extender e melhorar o protocolo \textit{Wireless Token Ring Protocol} (WTRP) ~\cite{ergen, top}, foco da dissertação de mestrado do Dr. Ergen ~\cite{ergenthesis}.  WTRP provê qualidade de
serviço (QoS) em termos de largura de banda reservada e latência limitada. Estas QoS são benéficas aos aplicativos que rodam em ambiente ad-hoc wireless.\\
WTRP como protocolo MAC distribuído é robusto contra queda de um nó e suporta as topologias flexiveis através de fato de cada nó ser parcialmente conectado (nem todos os nós precisam estar conectados entre si) 
 ~\cite{ergen}. Porém, WTRP apresenta algumas falhas. Em TRWC procuramos melhorar o desempenho de WTRP usando múltiplas transmissões simultâneas (através de múltiplos tokens) e
o consumo de energia. O TRWC é uma vertente diferente de WTRP com esquema de roteamento diferente. Ele tem a capacidade de formar aglomerado de nós participantes e também implementa mecanismo que permite
com que todos os nós tenham a vez de usar o token.

\section{Motivação}
           As redes ad-hoc wireless começaram com aplicações para comunicações militar, mas durante os anos oitenta e começo dos anos noventa a 
 pesquisa diminuiu devido a topologia complexa de rede ad-hoc wireless ~\cite{toumpis}. A chegada de rede de celulares sem fio
fez com que as pesquisas e desenvolvimentos em rede ad-hoc wireless crescessem (existem aplicações mais adequadas a esta última).  
Agora seriam necessários soluções que resolvessem os vários problemas existentes. Como é do nosso interesse, refiro a uso rigoroso e justo de largura de banda,
limite em tempo de pacote chegar ao destino e gerenciamento de consumo de energia.
         Nas próximas seções apresentamos alguns campos de aplicação do token ring.
	\subsection{Veículos}
	   \begin{itemize}
		\item Frota de veículos terrestres guiados por um mapa. Veículos em pontos diferentes registram no mapa o estado atual do tráfego na região.
                \item Veículos aéreos sem tripulante requerem um controle rígido de largura de banda, limite em latência e rapidez na cobertura de falha em protocolo de
                              acesso ao meio ~\cite{ergenthesis}.
             \end{itemize}
           \subsection{Multimedia}
	O compartilhamento de recursos é um desafio interessante para a rede ad-hoc móvel. Os recursos
          podem ser impressoras, jogos em dispositivos móveis, acesso a internet ou até mesmo a
          busca por um número limitado de informações ou itens (seja no campo, ou em outro ambiente qualquer).

\section{Problemas em rede ad-hoc}
Em redes ad-hoc wireless os nós estabelecem links entre si para as transmissões e recepções de dados. Para ter a hipótese de conseguir esse objetivo,
temos que considerar os desafios em assuntos de roteamento, topologia e gerenciamento de energia, e controle de acesso ao meio. Em roteamento temos problemas com a baixa capacidade
de transporte de dados devido à escassa largura de banda, e mudança rápida de topologia devido ao enfraquecimento de canal ou mobilidade de nós; certamente, quando um nó transmite
o sinal não só chega ao destinatário, mas também aos demais nós na vizinhança. Pela simplicidade e pelo fato de ser intuitivo, o protocolo transportador sensivel de acesso múltiplo (CSMA\footnote{Carrier Sense Multiple Access})
parece adequado ao ambiente wireless, porém esse protocolo não é adequado por causa de problemas \textit{hidden terminal} e \textit{exposed terminal} ~\cite{toumpis}.\\

\section{Metodologia}
	Para a realização deste trabalho pretendemos usar os seguintes instrumentos:
	\begin{itemize}
	 \item Pesquisa e consulta de trabalhos relacionados (artigos e dissertações).
	 \item Sistemas operacionais Ubuntu 10.04 LTS ou uma versão mais recente, e Microsoft windows XP SP2 - para o desenvolvimento e teste de software.
	 \item Ambiente de integração de desenvolvimento Eclipse Helios ou alguma versão mais recente e estável
	 \item Ambiente Kile versão 2.0.85 ou mais recente para edição de texto em Latex.
	 \item SVN para o controle de versão do projeto.
	 \item Linguagem de programação C Ansi para a codificação e teste em espaço usuário do linux.
	 \item Linguagem de programação JAVA 6 para o desenvolvimento de uma versão aplicativo para telefones celulares.
	\end{itemize}

\section{Objetivos}
Neste trabalho, temos como objetivos: implementar (em espaço usuário do linux) um sistema de software Token Ring ad-hoc wireless eficiênte para encaminhamento de
dados; testar esse mesmo sistema e analisar os resultados obtidos. Também, desenvolver uma versão aplicativo
para telefones celulares.

\chapter{Descrição de conceitos}

	\section{Tolerancia a falha em rede ad-hoc}
		Em redes ad-hoc wireless, o alcance de sinal de rádio transceptor é limitado e devido a mobilidade é normal que algum nó fique fora de alcance da sua rede.
		Por outro lado, rede ad-hoc wireless deve prover serviços em tempo real. Então, se faz necessário o fornecimento de mecanismos capazes de
		reparar as falhas e recuperar o funcionamento da rede.\\
		Existem diversos estudos sobre tolerância a falha em redes ad-hoc wireless. Para o nosso trabalho lemos alguns trabalhos relacionados a esse assunto (veja 3.1).
		
	\section{Token Ring}
	    Especificado por IEEE 802.5 controle de acesso ao meio ~\cite{trspec}, rede Token Ring consiste de conjunto de estações serialmente (concepção inicial) conectados.
          Essas estações formam um laço ou seja, se dispõem topologicamente em anel.\\
	    A estação no anel recebe a permissão para transmitir quando estiver com o token (frame utilizado para comunicação entre as estações). Após terminar a transmissão ou atingir o tempo máximo de uso de token,
          a estação passa o token para o seu sucessor. Quando o token chega a uma estação e esta não tem a intenção de usá-lo, ele é passado para a próxima estação.
	
\chapter{Trabalhos relacionados}
	Neste capítulo organizamos os trabalhos estudados em assuntos relacionados à tolerância a falha, token ring wireless e diversos.

           \section{Tolerância a falha em rede ad-hoc wireless móvel}
		
		Os artigos relacionados nesta seção permitiram avaliar as alternativas ao esquema em~\cite{ergen} para a recuperação a falha.
		\subsection{Designing Fault Tolerance Ad Hoc Wireless Networks}
			A dependência de localização de nós e broadcast são aspectos fundamentais a tolerância de falha (sobrevivência) em redes ad-hoc wireless. Em~\cite{kawahigashi}, Kawahigashi \textit{et} al. apresentam
			o problema de sobrevivência em rede ad-hoc como problema de otimização. Onde o objetivo é minimizar a retransmissão de informações entre nós (quanto menor saltos melhor). Os autores sugerem
			o uso de grade exagonal (poliedro), uma plataforma para o problema, e o uso de algoritmo heurísitico - algoritmo de fechamento - para resolver o problema. Esse algoritmo de fechamento é adaptável também ao caso
			de poliedros em camadas.

		\subsection{Fault Tolerance Increasing In Token Ring LANs}
			Este artigo apresenta o conceito e a descrição física de uma rede distribuída baseada em Token Ring.
			Casale \textit{et} al. propõem mecanismos de detecção e correção de erros em anel (quando transmissor/receptor falha ou acontece quebra). O foco do artigo são as falhas produzidas pelo
			hardware (falha de sinal ou alguma estação com comunicação defeituosa) de sistema Token Ring.

		\subsection{Distributed Fault-Tolerant Quality of Wireless Networks}
			Llewellyn \textit{et} al. abordam o problema de roteamento baseado em conjunto pré-definido de preferências de cliente (nó). Para isso, os autores apresentam um algoritmo de roteamento
			QoS baseado em cluster para redes ad-hoc móveis com o objetivo de prover tolerância a falha. Esse algoritmo é o protocolo EFDCB (Extended Fully Distributed Cluster-Based), 
			extensão de FDCB para prover escalabilidade, eficiência e tolerância a falha critica para manter conexões QoS em ambiente móvel. O algoritmo FDCB introduz qualidade de serviço em MANET.

   	\section{Token Ring wireless}
		Na tese de mestrado ~\cite{ergenthesis} e no artigo ~\cite{ergen} Ergen  \textit{et} al. apresentam o protocolo WTRP para rede de baixa escala.
		No capítulo introdutório definimos o WTRP, porém vamos estender a explicação.
		O WTRP é dinâmico para entrada e saída de nós, capaz de recuperar de múltiplas falhas simultâneas e resolve o problema de conectividade parcial. Resolve o desafio de conectividade parcial adicionando
		gerenciamento de conectividade, tokens especiais (solicitar sucessor, atribuir predecessor, atribuir sucessor, etc), novos timers e campos adicionais em tokens. Em WTRP o token é criado e deletado pelos nós
		e ele carrega  o identificador de nó proprietário do anel a qual pertence.\\
		No artigo ~\cite{top} Top \textit{et} al. apresentam uma versão de WTRP baseado em ~\cite{ergen} com propósito de melhorar consumo de energia e o rendimento em redes
		de baixa escala onde todos os nós se alcançam.\\
		Aplicada a rede wireless em área metropolitana (W-MAN) e com as suposições de transmissões \textit{full duplex}, e nós estáticos; Cheng \textit{et} al. ~\cite{cheng}
		propõem uma versão melhorado de WTRP ~\cite{ergen} no que diz respeito à uso de múltiplos tokens simultaneamente, consequentemente múltiplas transmissões simultâneas.
		No artigo ~\cite{deng} Deng \textit{et} al. fazem a análise de desempenho de WTRP ~\cite{ergen} e propõem um esquema para reduzir o consumo de energia. A idéia básica é ajustar o tempo máximo
        		permitido para um nó ter o token. Assim, um nó pode transmitir por mais tempo durante o ciclo de rotação de token quando a número de nós com pacotes a transmitir anel decresce. ~\cite{ergen} e 
		~\cite{top} são a base do nosso trabalho ao passo que ~\cite{cheng} e ~\cite{deng} serão considerados no sentido de conceber um sistema token ring que permita múltiplas transmissões e baixo consumo de
		energia.
	

	\section{Wireless ad-hoc networks and related topologies: applications and research challenges}
		Em ~\cite{toumpis}, Toumpis e Toumpakaris fazem uma síntese de conceitos de redes ad-hoc wireless, vantagens em relação às redes de arquitectura centralizada (topologia celular),
		pesquisas em andamento, desafios teóricos e técnicos, revisão histórica e alguns reparos sobre as aplicações (presente e futura) dessas redes. Este trabalho contribui em termos de
	          conceitos, aplicações e história da rede ad hoc wireless.


	\section{Fairness and QoS in Multihop Wireless Networks}
		Jun e Sichitiu abordam o problema de alocação de largura de banda com justiça em uma rede ad-hoc multihop. Apresentam um estudo teórico para garantir justiça e QoS baseado em diferentes esquemas
		de enfileiramento. Considerando os nós como roteadores, então elas podem retransmitir dados (\textit{relayed traffic}) e emitir dados (\textit{originating traffic}). \\
		Cada esquema supõe a existência de fila(s)  na camada de rede e também na camada de MAC: O esquema \textit{Isolate originating traffic} sugere o isolamento de \textit{originating traffic}
		colocando duas filas justas na camada de rede. Porém, esse esquema é justo somente se o número de saltos não excede 2; \textit{Different weight on the relayed traffic} é o esquema anterior
		com peso diferente para fila de \textit{relayed traffic}; \textit{Per-flow queuing} sugere uma fila para cada fluxo na camada de rede, independentemente de ser \textit{relayed traffic} ou \textit{originating traffic}.


\chapter{Proposta}

%\chapter{Descrição do projeto e estado atual}

       \section{Definições}
          \begin{itemize}
                \item Para um determinado nó, endereço MAC e o ID serão considerados sinónimos.
                \item O nó participante é o nó envolvido no anel. O nó não participante é o oposto.
		\item O proprietário é o nó a quem pertence o anel.
		\item O nó predecessor é aquele que passa o token ao nó atual. O nó sucessor é aquele que recebe o token do nó atual.
		\item Utilizaremos a palavra frame para descrever sequência de bits enviados para a camada física.
		\item Anel varal é a estrutura em anel onde os \textit{gateways} são pendurados. Utilizaremos o termo varal ao invés de anel varal.
		\item \textit{gateway} é o nó que pertence a dois anéis (o seu próprio anel e o varal)
		\item Canal é o meio compartilhado pelos nós de mesmo anel para a trocar de informações.
	  \end{itemize}

           \subsection{Observações}
	Manteremos as denominações apresentadas em ~\cite{ergenthesis} sempre que for mais conveniente.

	
	\section{Descrição do projeto}
	 %Na seção 2.1 introduzimos de forma sucinta o nosso projeto. Ele consiste em implementar o sistema Token Ring wireless baseado em \textit{clusters}.\\
	    
	    Propomos implementar um TRWC - \textit{cluster} de nós em anéis múltiplos. Para cada anel temos um canal diferente.\\
	  Em TRWC dividimos o roteamento em dois, à saber: roteamento intra-anel e inter-anel.\\
	  O roteamento intra-anel é o roteamento entre nós que pertencem ao mesmo anel. E o roteamento entre os \textit{gateways}
	  é denominado roteamento inter-anel.\\
	  Cada  \textit{gateway} possui as informações de todos os nós em seu anel. Assim, se o destinatário não pertencer ao mesmo anel que o remetente,
	  os dados são encaminhados de remetente para o seu \textit{gateway}, deste para o \textit{gateway} destino e deste último para o destinatário.\\
	  Eventualmente, se o \textit{gateway} falhar podemos eleger algum nó no seu anel para sucessor. Para encontrar esse \textit{gateway} sucessor, podemos fazer uma eleição
	  entre os nós de \textit{gateway} cessante.\\
            O Token Ring wireless baseado em \textit{cluster} possui um anel varal que é exclusivamente formado pelos \textit{gateways}. Se existe pelo menos dois nós participantes
           e se todos esses participantes tiverem predecessor e sucessor então está formado algum tipo de anel.
	  Em TRWC, um nó envia dados somente após receber o token do seu predecessor e após terminar passa o token para o seu sucessor.\\

	\begin{table}[!h]
		\begin{tabular}[c]{|c|c|c|c|c|c|c|c|} 
			\hline 
			FC & IR & RA & SA & DA & Seq & GenSeq & Num\\ 
			\hline
		\end{tabular}
           \caption[Short]{Frame do Token}
          \end{table}	

	A Tabela 4.1 ilustra o \textit{frame} de token.
	\begin{itemize}
		\item \textbf{FC} é o campo que identifica o tipo de pacote (a ser especificado mais adiante).
		\item \textbf{IR} informa se o \textit{frame} pertence ao anel varal ou não.
		\item \textbf{RA} identifica o endereço do anel que detém o token.
		\item \textbf{SA} identifica o endereço de nó remetente.
		\item \textbf{DA} identifica o endereço de nó destinatário.
		\item \textbf{Seq} identifica o número de sequência do token. Seq é inicializada em zero e incrementada em cada nó que passa o token.
		\item \textbf{GenSeq} define sequência de geração de token. Inicializada em zero e incrementada pelo proprietário a cada rodada completa de token.
		\item \textbf{Num} informa o número de nós no anel e é útil para elimina interferência.
	\end{itemize}

	Os tipos de pacotes são: \textit{Token, Claim Token, Solicit Sucessor, Set Predecessor, Set Sucessor, Deleted Token}.

	\subsection{A escolha de proprietário}
		 O nó gerador de token é o proprietário do anel. Para registrar essa informação existe um campo específico (RA) em token dentre vários. O proprietário prevalece até
	   que ele seja não participante ou interrompido\footnote{falha por causa de baixo sinal, bateria fraca, ou qualquer problema no dispositivo}. No primeiro caso, ao sair, o sucessor
              do proprietário cessante assume a função de proprietário do anel registrando o seu ID no campo específico de token. Mais adiante esclareceremos o tratamento no caso de proprietário
              ser interrompido.\\

		O mecanismo através do qual o nó monitora se a transmissão de token foi bem sucedida, chama-se \textbf{ACK implícito}.
	 	ACK implícito (ACK) é qualquer pacote escutado após a transmissão de token que tem mesmo endereço de anel que o nó. Pode ser também, qualquer transmissão partindo de nó alcançável
		com destino a qualquer anel ~\cite{ergenthesis}.

	\subsection{Controle de conectividade}
	    Cada nó possui um gerenciador de conectividade que registra as transmissões que ocorrem em seu anel e anéis próximos. Para tal, o gerenciador de conectividade monitora o número de sequência (Seq)
	 de tokens transmitidos e registra as informações de nós na sua tabela de conectividade. Nessa tabela lista informações de nós em seu anel de maneira ordenada
           e de nós em anéis vizinhos de maneira não ordenada. Por exemplo, na tabela 4.1 apresentamos o alcance de transmissão do nó A que corresponde à tabela (4.2) de conectividade.
	 Podemos ver que em B o Seq é incrementado para 1, como A não escuta a transmissão em E, ele vai receber o token com Seq valendo 3. Então, o nó A conclui que entre os nós B e C existe um nó que ele
	 não consegue escutar.\\
	Note que cada nó pode ter duas listas ordenadas (T1 e T2) porque ele pode ser um \textit{gateway}, e uma lista desordenada \underline{alcançáveis} com nós alcançáveis (caso do nó D na figura 4.1),
	porém não presente no mesmo anel.

	\begin{figure} \centering
	\begin{tikzpicture}[xscale=6, yscale=8,>=stealth]
		\node[circle,inner sep=0pt,minimum size=4.2cm,draw, dashed] at (0,-0.3){};
		\tikzstyle{v}=[circle,inner sep=0pt,minimum size=0.1mm,draw,thick]
		\node[v] (e) {$E$};
		\node[v] (f) [right =of e]{$F$};
    		\node[v] (c) [below right =of e] {$C$};
    		\node[v] (b) [below left=of e] {$B$};
		\node[v] (a) [below right=of b] {$A$};
		\node[v] (d) [below=of a] {$D$};
    		\draw[thick,->] (a) to node {} (b);
    		\draw[thick,->] (c) to node {} (a);
		\draw[thick,->] (b) to node {} (e);
		\draw[thick,->] (e) to node {} (c);
	\end{tikzpicture}
		\caption{Área de alcance do nó A}
	\end{figure}


	\begin{table}[h!]
	\vspace{5pt}

    	\begin{center}
	\begin{tabular}{|c|}
	\hline
        		\subtable
            	{    
                			\begin{tabular}{|c|c||c|c|} 
				\hline
				\multicolumn{4}{|c|}{Listas}\\\hline
				\hline
				\multicolumn{2}{|c|}{\textbf{T1}} & \multicolumn{2}{c|}{\textbf{T2}} \\\hline
				$ID$ & $Seq$ & $ID$ & $Seq$ 			         \\\hline
				B & 1               &  - & -                                                 \\\hline
				? & 2      	  &  - & -                                                 \\\hline
				C & 3     	  &  - & -                                                 \\
				\hline
				\end{tabular}\tiny \centering
            	}
        		\subtable
            	{
            		\begin{tabular}{|c|}
            		\hline
			Alcançáveis \\\hline
			\hline
			E \\
			\hline
			\end{tabular}\tiny \centering
            	}\\
		\hline
	    	\end{tabular}    
        		\caption[Short]{Tabela de conectividade do nó A}
		%\label{tab:chapter4:1}
	    \end{center}
\end{table}

	\subsection{Procedimento de encontrar sucessor}
	Quando o nó não recebe ACK depois de algumas tentativas de passar o token , assume que o sucessor não está presente. Então, invoca o mecanismo de recuperação de anel
	que tenta formar o anel novamente pela estratégia de excluir o menor número de nós possível da sua tabela de conectividade. Ao encontrar nó disponível para
	fechar o anel, o nó envia o token correspondente à mensagem ``atribuição de predecessor".\\
          Quando o nó decide solicitar um sucessor seu serviço de admissão faz \textit{broadcast} enviando um token correspondente à mensagem ``solicitar sucessor" e espera que os interessados peguem os lugares na sala de resposta. Algum 
	nó interessado em se juntar ao anel, ao escutar a mensagem de ``solicitação de sucessor"  pega o lugar na sala de resposta enviando a mensagem correspondente à ``atribuição de sucessor". À propósito, o nó que deseja entrar no anel tem que
	aguardar até que algum nó presente no anel solicite o sucessor através de \textit{broadcast} acima. Por exemplo, na figura 4.2 o nó D deseja entrar no anel. Suponhamos que o nó B faça \textit{broadcast} solicitando sucessor. O nó D
	escuta a transmissão feita pelo B, pega o lugar na sala de resposta enviando ``atribuição de sucessor". Supondo que o nó B decidiu que dentre os interessados o vencedor é o D. Então, o B passa o token correspondente à mensagem 
	``atribuição de predecessor" ao D e este último passa o token ``atribuição de predecessor" ao A (sucessor de B até então).

	\begin{figure}[!h]\centering
	\begin{tikzpicture}[xscale=6, yscale=8,>=stealth]
		\tikzstyle{v}=[circle,inner sep=0pt,minimum size=0.1mm,draw,thick]
    		\node[v] (c) at (0,0) {$C$};
    		\node[v] (b) [right=of c] {$B$};
		\node[v] (a) [below=of b] {$A$};
		\node[v] (d) [above right=of a,below right=of b] {$D$};
    		\draw[thick,->] (a) to node {} (c);
    		\draw[thick,->] (c) to node {} (b);
		\draw[thick,->] (b) to node {} (a);
		\draw[dashed,->] (b) to node {} (d);
		\draw[dashed,->] (d) to node {} (a);
	\end{tikzpicture}
		\caption{Entrada do nó D}
	\end{figure}
	\subsection{Procedimento de saída em anel}
		Suponhamos que D deseja sair do anel como mostra a figura 4.3. Primeiro, o nó D deve aguardar a sua vez de transmitir. Ao receber o token, ele manda o token correspondente à mensagem (com ID de A) ``atribuição de sucessor" 
		para o seu predecessor B. Se o nó A está ao alcance de transmissão do B, então este último tenta conectar ao A enviando o token ``atribuição de sucessor". Senão, o B procura por ordem na sua tabela de conectividade
		o próximo nó para tentar a conexão enviando o token ``atribuição de sucessor.
		\begin{figure}\centering
	\begin{tikzpicture}[xscale=6, yscale=8,>=stealth]
		\tikzstyle{v}=[circle,inner sep=0pt,minimum size=0.1mm,draw,thick]
    		\node[v] (c) at (0,0) {$C$};
    		\node[v] (b) [right=of c] {$B$};
		\node[v] (a) [below=of b] {$A$};
		\node[v] (d) [above right=of a,below right=of b] {$D$};
    		\draw[thick,->] (a) to node {} (c);
    		\draw[thick,->] (c) to node {} (b);
		\draw[dashed,->] (b) to node {} (a);
		\draw[thick,->] (b) to node {} (d);
		\draw[thick,->] (d) to node {} (a);
	\end{tikzpicture}
		\caption{Saída do nó D}
	\end{figure}	

	\subsection{Gerenciamento de token}
	Como já referimos resolvemos o problema de conectividade parcial utilizando tokens especias. Para gerenciar múltiplos tokens atribuimos prioridades aos mesmos. A sequência
	de geração GenSeq define a prioridade. O token com GenSeq mais alto tem a prioridade mais alta. Quando tokens têm GenSeq iguais, o ID de proprietários desempata. O nó também tem
           a sua prioridade. Esta é a prioridade do último token que o nó aceitou ou o nó gerou.\\
	Quando o nó recebe o token, verifica se este último tem a prioridade maior que ele. Se o token não tiver prioridade maior, o nó deleta o token recebido (sem aceitá-lo) e notifica o seu predecessor. Assim, é possível
	deletar tokens excepto um.

          \subsection{Observações} 
            Somente os \textit{gateways} podem figurar em varal e em seu próprio anel.\\
            Somente nó que tenha informações a enviar deve fazer parte do anel.\\
	
	%\section{Andamento do projeto}
\chapter{Cronograma}

    \begin{itemize}
    \item Nos próximos 4 meses terei o código do sistema TRWC funcionando no espaço usuário do linux.
    \item 1 mês para rodar testes.
    \item 6 meses para reforçar os estudos em assuntos relacionados e a redação da dissertação.
    \item 2 meses para a elaboração de artigos.
    \item A defesa do trabalho.
    \item Alterações sugeridas pela banca.
    \end{itemize}

\begin{thebibliography}{99}
 \bibitem{ergenthesis} Ergen, M. ``WTRP - Wireless Token Ring Protocol". Dissertação de mestrado. 2002
 \bibitem{ergen} \href{http://wow.eecs.berkeley.edu/ergen/docs/WTRP_SCI02.pdf}{Ergen, M.;Lee, D.;Puri, A.;Varaiya, P.; Wireless Token Ring Protocol. 2002.}
 \bibitem{top} Top, F.;Kohlhepp, V.;Dowla, F.; A Token Ring Protocol for Dynamic Ad-hoc Wireless Environments.
 \bibitem{toumpis} Toumpis, S.;Toumpakaris, D.; Wireless ad hoc networks and related topologies: applications and research challenges. Elektrotechnik and Informationstechnik (February, 2006), pp. 232-241.
 \bibitem{jun} Jun, J.;Sichitiu, M.; Fairness and QoS in Multihop Wireless Networks. Vehicular Technology Conference, 2003, Vol. 5, (October, 2003), pp. 2936 - 2940.
 \bibitem{kawahigashi} Kawahigashi, H.; Terashima, Y.; Miyauchi, N.; Nakakawaji, T.;Designing Fault Tolerance Ad Hoc Wireless Networks. Military Communications Conference, 2005. Vol. 3, (October ,2005), pp. 1360 - 1367.
 \bibitem{casale} Casale, S.; Catania, V.; Vita, L.; Fault Tolerance Increasing In Token Ring LANs. Local Computer Networks, 1988. (October, 1988), pp. 446 - 452. 
 \bibitem{llewellyn} Llewellyn, L.C.; Hopkinson, K.M.; Graham, S.R.; Distributed Fault-Tolerant Quality of Wireless Networks. Mobile Computing, IEEE Transactions on. Vol. 10, (February, 2011), pp. 175 - 190.
 \bibitem{lauf}Lauf, A.P.; Robinson, W.H.; Fault Tolerance in MANETs Using a Task-to-Resource Reallocation Framework. Computational Science and Engineering, 2009. CSE '09. International Conference on. Vol. 2, (August, 2009), pp. 753 - 758.
 \bibitem{trspec} \href{http://voiplab.niu.edu.tw/IEEE/802.5/802.5v-2001.pdf}{ANSI/IEEE Standard 802.5v 2001 (aperfeiçoamento 1999) : ``Token Ring access method and physical layer specifications'', IEEE 2001.}
 \bibitem{cheng} Cheng, R.G.; Chang, R.I.; Hua, K.L.; IWTRP: Spatial-reuse Enhancement of the Wireless Token Ring Protocol.  Communications Letters, IEEE, 2007. Vol. 11,(August, 2007), pp.701 - 703.     %Nat. Taiwan Univ. of Sci. & Technol., Taipei 
 \bibitem{deng} Deng Z.; Lu  Y.; Wang C.; Wang  W.; E$^2$WTRP: an energy-efficient wireless token ring protocol. Personal, Indoor and Mobile Radio Communications, 2004. PIMRC 2004. 15th IEEE International Symposium on. Vol. 1, (September, 2004), pp. 574-578.
\bibitem{wifispec}\href{http://standards.ieee.org/getieee802/download/802.11-2007.pdf}{IEEE Standard 802.11v 2007: ``Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications'', IEEE 2007.}
\end{thebibliography}
\end{document}